package leetcode.pre100;


import utils.ListNode;

/**
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * 示例 2:
 * <p>
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 * <p>
 *
 * @date 2020/2/28 22:39
 */
public class Code83_DeleteRepeatNode_删除链表重复元素2 {
    public static void deleteRepeat(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode cur = new ListNode(-1);
        ListNode p = head;
        boolean repeat = false;
        while (p != null) {
            ListNode next = p.next;
            //重复的点的尾巴
            ListNode lastRepeat = p;
            //这一段判重
            while (next != null && (p.val == next.val)) {
                lastRepeat = next;
                next = next.next;
                repeat = true;
            }
            if (repeat) {
                //之前的pHead  - lastRepeat 都是重复，GC。
                // 不用管pHead-lastRepeat也行,但是会造成内存泄漏
                lastRepeat.next = null;
                //找到新的开始的头pHead,
                p = next;
                repeat = false;
            } else {
                //把cur和pHead连接起来
                cur.next = p;
                cur = cur.next;
                p = p.next;
            }
        }
        //考虑最后两个重复的情况，如1,4,4  cur = 1.其next没有置空
        cur.next = null;
    }

    //递归版本
    public ListNode deleteDuplication3(ListNode p) {
        if (p == null || p.next == null) { // 只有0个或1个节点
            return p;
        }
        // 当前节点是重复节点
        if (p.val == p.next.val) {
            ListNode node = p.next;
            while (node != null && node.val == p.val) {
                // 跳过值与当前节点相同的全部节点，找到第一个与当前节点不同的节点
                node = node.next;
            }
            // 从第一个与当前结点不同的结点继续递归.
            // node一定不和phead等。也就是说相等的不会被加入链表。
            return deleteDuplication3(node);
        } else {
            // 保留当前节点，从下一个节点继续递归。
            // 并把当前节点返回给上一级。
            p.next = deleteDuplication3(p.next);
            return p;
        }

    }

    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        pHead.next = new ListNode(1);
        pHead.next.next = new ListNode(2);
        pHead.next.next.next = new ListNode(3);
        pHead.next.next.next.next = new ListNode(3);
        deleteRepeat(pHead);
        while (pHead != null) {
            System.out.print(pHead.val + " ");
            pHead = pHead.next;
        }
    }

}
